home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / hotjava / classsrc / browser / tools / javase~1 / idvect~1.jav < prev    next >
Encoding:
Text File  |  1995-08-11  |  7.4 KB  |  260 lines
  1. /*
  2.  * @(#)IDVector.java    1.10 95/03/14 David A. Brown
  3.  *
  4.  * Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software
  7.  * and its documentation for NON-COMMERCIAL purposes and without
  8.  * fee is hereby granted provided that this copyright notice
  9.  * appears in all copies. Please refer to the file "copyright.html"
  10.  * for further important copyright and licensing information.
  11.  *
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  13.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  14.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  15.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  16.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  17.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  18.  */
  19.  
  20. package browser.tools.JavaSearch;
  21.  
  22. /** 
  23.  *  Vector of JavaSearch Doc IDs.  Doc IDs are chars.
  24.  *  There are 'count' valid IDs in ids[].  The IDs in ids[]
  25.  *  are always guaranteed to be in ascending order.
  26.  *
  27.  *  This class implements some basic functions 
  28.  *  performed on lists of Doc IDs by the JavaSearch indexer
  29.  *  and searcher.
  30.  *  
  31.  */
  32. public class IDVector {
  33.  
  34.     /** Array of IDs */
  35.     public char ids[];
  36.     
  37.     /** Current Number of IDs in the array */
  38.     public int count = 0;
  39.  
  40.     /** Basic IDVector constructor */
  41.     public IDVector() {
  42.         ids = new char[64];
  43.     }
  44.  
  45.     /** Make sure we have room to hold at least 'minimumCapacity' IDs */
  46.     private synchronized void ensureCapacity(int minimumCapacity) {
  47.         int maxCapacity = ids.length;
  48.  
  49.         if (minimumCapacity > maxCapacity) {
  50.             int newCapacity = (maxCapacity + 1) * 2;
  51.             if (minimumCapacity > newCapacity) {
  52.                 newCapacity = minimumCapacity;
  53.             }
  54.  
  55.             char newIDs[] = new char[newCapacity];
  56.             System.arraycopy(ids, 0, newIDs, 0, count);
  57.             ids = newIDs;
  58.         }
  59.     }
  60.  
  61.     /** 
  62.      *  Append the specified Doc ID to our array of doc IDs.
  63.      * 
  64.      *  Note that any given Doc ID should only appear once
  65.      *  in our array!  But since the indexer processes only one
  66.      *  doc at a time, all we have to do is check 'id' against
  67.      *  the *most recent* addition to our array.  If the specified
  68.      *  id is equal to the id we last added, just do nothing.
  69.      */
  70.     public synchronized void appendID(char id) {
  71.     if ((count > 0) && (ids[count-1] == id)) {
  72.         return;
  73.     }
  74.     ensureCapacity(count + 1);
  75.     ids[count++] = id;
  76.     //System.out.println("  appendDocId was successful: "+this);
  77.     }
  78.  
  79.     /** Clear this IDVector; reset it to a count of zero. */
  80.     public void clear() {
  81.     count = 0;
  82.     }
  83.  
  84.  
  85.     //
  86.     // Methods implementing boolean "Doc ID list merging".
  87.     // These are how the Search engine implements AND, OR and NOT.
  88.     //
  89.  
  90.     /**
  91.      * Intersect this IDVector with another IDVector.
  92.      * This IDVector is modified to contain only IDs
  93.      * found in BOTH this and aVector.
  94.      *
  95.      * This vector's count is guaranteed to become at least
  96.      * as small as min(count, aVector.count), ie. it certainly
  97.      * will NOT become any larger.
  98.      */
  99.     public void intersectWith(IDVector aVector) {
  100.  
  101.     //System.out.println("IDVector.intersectWith...");
  102.     //System.out.println("  this IDVector is: "+this);
  103.     //System.out.println("        aVector is: "+aVector);
  104.  
  105.     // Allocate an array as large as we might possibly need
  106.     char newids[] = new char[Math.min(count, aVector.count)];
  107.     int newcount = 0;
  108.  
  109.     // Our IDs are in ids[], from 0 to count-1.
  110.     // IDs to merge in are in aVector.ids[], from 0 to aVector.count-1.
  111.     int aa = 0;
  112.     int bb = 0;
  113.     while (aa<count && bb<aVector.count) {
  114.  
  115.         // Check both ID lists.  If both lists have the same
  116.         // ID, add it to newids.  Otherwise, advance the pointer
  117.         // of whichever list had the lower ID.
  118.         if (ids[aa] == aVector.ids[bb]) {
  119.         newids[newcount++] = ids[aa++];
  120.                 bb++;
  121.         }
  122.         else if (ids[aa] < aVector.ids[bb]) {
  123.         aa++;
  124.         }
  125.         else {  // ids[aa] > aVector.ids[bb]
  126.         bb++;
  127.         }
  128.     }
  129.  
  130.     // Done merging.  Install newids[] and newcount.
  131.     ids = newids;
  132.     count = newcount;
  133.     //System.out.println("After INTERSECT, this IDVector is: "+this);
  134.     }
  135.  
  136.     /**
  137.      * Intersect this IDVector with the OPPOSITE of another IDVector.
  138.      * This IDVector is modified to contain only IDs
  139.      * found in this vector and NOT in aVector.
  140.      *
  141.      * This vector's count is guaranteed to NOT become any larger.
  142.      */
  143.     public void intersectWithNot(IDVector aVector) {
  144.  
  145.     //System.out.println("IDVector.intersectWithNot...");
  146.     //System.out.println("  this IDVector is: "+this);
  147.     //System.out.println("        aVector is: "+aVector);
  148.  
  149.     // Allocate an array as large as we might possibly need
  150.     char newids[] = new char[count];
  151.     int newcount = 0;
  152.  
  153.     // Our IDs are in ids[], from 0 to count-1.
  154.     // IDs to NOT with are in aVector.ids[], from 0 to aVector.count-1.
  155.     int aa = 0;
  156.     int bb = 0;
  157.     while (aa<count) {
  158.  
  159.         // Make sure bb is pointing at the next possible conflict:
  160.         //   aVector.ids[bb] must be >= ids[aa]
  161.         while ((aVector.ids[bb]<ids[aa]) && (bb < aVector.count)) {
  162.         bb++;
  163.         }
  164.            
  165.         if (bb == aVector.count) {
  166.         // Ran out of entries in aVector.  Just take our IDs.
  167.         newids[newcount++] = ids[aa++];
  168.         }
  169.         else {
  170.         // If aVector.ids[bb] == ids[aa], DON'T include
  171.         //   it in the result.  Otherwise, use one more
  172.         //   entry from ids[].
  173.         if (aVector.ids[bb] == ids[aa]) {
  174.             aa++;
  175.             bb++;
  176.         }
  177.         else {
  178.             newids[newcount++] = ids[aa++];
  179.         }
  180.         }
  181.     }
  182.  
  183.     // Done merging.  Install newids[] and newcount.
  184.     ids = newids;
  185.     count = newcount;
  186.     //System.out.println("After NOT, this IDVector is: "+this);
  187.     }
  188.  
  189.     /**
  190.      * Union this IDVector with another IDVector.
  191.      * This IDVector is modified to contain IDs
  192.      * found in EITHER this or aVector.
  193.      *
  194.      * This vector's count may become larger than it was,
  195.      * and may in fact become as large as (count + aVector.count).
  196.      */
  197.     public void unionWith(IDVector aVector) {
  198.     
  199.     //System.out.println("IDVector.unionWith...");
  200.     //System.out.println("  this IDVector is: "+this);
  201.     //System.out.println("        aVector is: "+aVector);
  202.  
  203.     // Allocate an array as large as we might possibly need
  204.     char newids[] = new char[count + aVector.count];
  205.     int newcount = 0;
  206.  
  207.     // Our IDs are in ids[], from 0 to count-1.
  208.     // IDs to merge in are in aVector.ids[], from 0 to aVector.count-1.
  209.     int aa = 0;
  210.     int bb = 0;
  211.     while (aa<count || bb<aVector.count) {
  212.  
  213.         if (aa>=count) {
  214.         // Hit end of our IDs, just take entries from aVector
  215.         newids[newcount++] = aVector.ids[bb++];
  216.         }
  217.         else if (bb>=aVector.count) {
  218.         // Hit end of aVector's IDs, just take entries from ids[]
  219.                 newids[newcount++] = ids[aa++];
  220.             }
  221.         else {
  222.         // Still processing both ID lists.  Take whichever's lower.
  223.         if (ids[aa] < aVector.ids[bb]) {
  224.             newids[newcount++] = ids[aa++];
  225.         }
  226.         else if (ids[aa] > aVector.ids[bb]) {
  227.             newids[newcount++] = aVector.ids[bb++];
  228.         }
  229.         else {
  230.             // Both lists had the same ID!
  231.             newids[newcount++] = ids[aa++];
  232.             bb++;
  233.         }
  234.         }
  235.  
  236.     }
  237.  
  238.     // Done merging.  Install newids[] and newcount.
  239.     ids = newids;
  240.     count = newcount;
  241.     //System.out.println("After UNION, this IDVector is: "+this);
  242.     }
  243.  
  244.     /** Generate a simple printed representation of this IDVector */
  245.     public String toString() {
  246.     String s = "IDVector ["+count+"]:";
  247.     for (int i=0; i<count; i++) {
  248.         s += " " + (int)ids[i];
  249.     }
  250.     return s;
  251.     }
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259. }
  260.